﻿// Copyright (c) 2012 - 2020 Jared Zheng <jaredz at outlook dot com>
// Buddha Framework is licensed under Mulan PSL v2.
// You can use this software according to the terms and conditions of the Mulan PSL v2.
// You may obtain a copy of Mulan PSL v2 at:
//          http://license.coscl.org.cn/MulanPSL2
// THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
// EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
// MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
// See the Mulan PSL v2 for more details.
//
// Create : 2012-12-01 version 0.1 Jared Zheng <jaredz at outlook dot com>
// Update : 2018-12-05 version 3.1.5 Jared Zheng <jaredz at outlook dot com>

#ifndef __SERVER_SORT_INL__
#define __SERVER_SORT_INL__

#pragma once

///////////////////////////////////////////////////////////////////////////////////////////////////////////
// tagSERVER_SORT : 快速排序服务器负载情况
INLINE void tagQUICK_SORT::QuickSort(tagSERVER_SORT* pSort, Int nCount)
{
    QuickSortRecursion(pSort, 0, nCount);
}
// 排序的递归调用
INLINE void tagQUICK_SORT::QuickSortRecursion(tagSERVER_SORT* pSort, Int nBegin, Int nEnd)
{
    if (nBegin < (nEnd - 1))
    {
        // 如果区域不存在或只有一个数据则不递归排序
        // 这里因为分割的时候, 分割点处的数据就是排序中他的位置
        // 也就是说他的左边的数据都小于等于他, 他右边的数据都大于他
        // 所以他不在递归调用的数据中
        Int nPart = Partition(pSort, nBegin, nEnd);  // 找到分割点
        QuickSortRecursion(pSort, nBegin, nPart);    // 递归左边的排序
        QuickSortRecursion(pSort, nPart + 1, nEnd);  // 递归右边的排序
    }
}
// 化分区间, 找到最后元素的排序位置, 并返回分隔的点(即最后一数据排序的位置)
// 划分的区间是[nBegin, nEnd), pSort是保存数据的指针
INLINE Int tagQUICK_SORT::Partition(tagSERVER_SORT* pSort, Int nBegin, Int nEnd)
{
    Int nPart = nBegin - 1;    // 最后Comp保存在这里
    --nEnd;

    tagSERVER_SORT Temp;       // 交换用的临时数据
    tagSERVER_SORT Comp = pSort[nEnd]; // 比较的数据

    // 遍历数据比较, 找到Comp的位置, 这里注意, 比较结果是:
    // 如果i的左边是小于等于Comp的, i的右边是大于Comp的
    for (Int i = nBegin; i < nEnd; ++i)
    {
        if (pSort[i].usLoad <= Comp.usLoad)
        { // 如果数据比要比较的小, 则在该数据的左边, 与 nPart + 1 交换
            ++nPart;                         // 小于Comp的数据多一个, 所以要加1, i的左边数据都比Comp小
            Temp         = pSort[nPart];     // 交换数据
            pSort[nPart] = pSort[i];
            pSort[i]     = Temp;
        }
    }
    // 最后不要忘了把Comp和 nPart + 1 交换, 因为这里就是Comp的位置
    ++nPart;
    pSort[nEnd]  = pSort[nPart];
    pSort[nPart] = Comp;

    return nPart;   // 返回nPart的位置, 就是分割的位置
}

INLINE tagQUICK_SORT::tagQUICK_SORT(void)
{
}

INLINE tagQUICK_SORT::~tagQUICK_SORT(void)
{
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////
// tagSORT_RESULT : 服务器按负载情况排序结果数组
INLINE tagSORT_RESULT::tagSORT_RESULT(void)
: uIndex(0)
, uCount(0)
{
    Sort.SetGrow(DATAD_SORT);
}

INLINE tagSORT_RESULT::~tagSORT_RESULT(void)
{
}

INLINE void tagSORT_RESULT::Reset(void)
{ 
    uIndex = 0; 
    uCount = 0;
    Sort.RemoveAll();
}

INLINE void tagSORT_RESULT::Count(UInt uAddCount)
{
    uCount = uAddCount;
}

INLINE UInt tagSORT_RESULT::Index(void)
{
    UInt uCurr = CAtomics::CompareExchange<UInt>(&uIndex, 0, 0);
    CAtomics::Exchange16<Short>((PShort)&Sort[uCurr].usLoad, (Sort[uCurr].usLoad + Sort[uCurr].usIncr));
    if (uCount > 2)
    {
        UInt uPrev = (uCurr == 0) ? (uCount - 1) : (uCurr - 1);
        UInt uNext = (uCurr == (uCount - 1)) ? 0 : (uCurr + 1);
        if (CAtomics::CompareExchange16<Short>((PShort)&Sort[uCurr].usLoad, 0, 0) > Sort[uNext].usLoad)
        {
            CAtomics::Exchange<UInt>(&uIndex, uNext);
        }
        else if (CAtomics::CompareExchange16<Short>((PShort)&Sort[uCurr].usLoad, 0, 0) > Sort[uPrev].usLoad)
        {
            CAtomics::Exchange<UInt>(&uIndex, uPrev);
        }
    }
    else if (uCount > 1)
    {
        UInt uNext = (uCurr == 0) ? 1 : 0;
        if (CAtomics::CompareExchange16<Short>((PShort)&Sort[uCurr].usLoad, 0, 0) > Sort[uNext].usLoad)
        {
            CAtomics::Exchange<UInt>(&uIndex, uNext);
        }
    }
    return uCurr;
}

INLINE UInt tagSORT_RESULT::Find(ULLong ullKey)
{
    UInt uCurr = uCount;
    for (UInt i = 0; i < (UInt)Sort.GetSize(); ++i)
    {
        if (Sort[i].ullKey == ullKey)
        {
            uCurr = i;
            break;
        }
    }
    if (uCurr != uCount)
    {
        CAtomics::Exchange16<Short>((PShort)&Sort[uCurr].usLoad, (Sort[uCurr].usLoad + Sort[uCurr].usIncr));
    }
    return uCurr;
}

INLINE UShort tagSORT_RESULT::MaxLoad(void)
{
    if (uCount > 0)
    {
        return Sort[uCount - 1].usLoad;
    }
    return 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////
// tagRESULT_CHAIN : 服务器按负载情况排序结果数组交换链
INLINE tagRESULT_CHAIN::tagRESULT_CHAIN(void)
: uIndex(0)
{
}

INLINE tagRESULT_CHAIN::~tagRESULT_CHAIN(void)
{
}

INLINE void tagRESULT_CHAIN::Reset(void)
{
    uIndex = 0;
    Result[0].Reset();
    Result[1].Reset();
}

INLINE void tagRESULT_CHAIN::Swap(void)
{
    if (CAtomics::CompareExchange<UInt>(&uIndex, 1, 0) != 0)
    {
        CAtomics::Decrement<UInt>(&uIndex);
    }
}

INLINE SORT_RESULT& tagRESULT_CHAIN::GetCur(void)
{
    return Result[uIndex];
}

INLINE SORT_RESULT& tagRESULT_CHAIN::GetNext(void)
{
    if (CAtomics::CompareExchange<UInt>(&uIndex, 0, 0) != 0)
    {
        Result[0].Reset();
        return Result[0];
    }
    else
    {
        Result[1].Reset();
        return Result[1];
    }
}

#endif // __SERVER_SORT_INL__
